##########################
# 邻接表图（Graph）和顶点（Vertex）类
# @Author: MK
# @CreateDate: 2023/10/05
##########################
MAX_INT = 2147483647


class Vertex:
    def __init__(self, key):
        self.id = key
        self.connectTo = {}
        self.distance = MAX_INT
        self.lastVertexKey = None

    # 添加该点的相邻点
    def addNeighbor(self, neighborId, weight=0):
        self.connectTo[neighborId] = weight

    # __str__函数，重定义print(Vertex)时输出的信息
    def __str__(self):
        return str(self.id) + ' connect to: ' + str([key for key in self.connectTo])

    # 清空路径信息
    def reload(self):
        self.distance = MAX_INT
        self.lastVertexKey = None


class Graph:
    def __init__(self):
        self.vertexDict = {}
        self.count = 0

    def addVertex(self, key):
        self.count = self.count + 1
        tempVertex = Vertex(key)
        self.vertexDict[key] = tempVertex

    def getVertex(self, n):
        if n in self.vertexDict:
            return self.vertexDict[n]
        else:
            return None

    def addEdge(self, fromVertex, toVertex, weight=0):
        if fromVertex not in self.vertexDict:
            self.addVertex(fromVertex)
        if toVertex not in self.vertexDict:
            self.addVertex(toVertex)
        self.vertexDict[fromVertex].addNeighbor(self.vertexDict[toVertex], weight)

    def getVertices(self):
        return self.vertexDict.keys()

    def __contains__(self, key):
        return key in self.vertexDict

    def __iter__(self):
        return iter(self.vertexDict.values())

    def findPath(self, fromVertex='start', toVertex='end'):
        pathStr = 'no path'
        if fromVertex not in self.vertexDict or toVertex not in self.vertexDict:
            return -1, pathStr
        usableDict = {'start': 0}
        while len(usableDict) > 0:
            currentVertexName = self.getShortest(usableDict)
            # 如果已经到达了目标，可以提前结束
            if currentVertexName == toVertex:
                return self.vertexDict[toVertex].distance, self.getPathStr(toVertex)
            # 否则，继续寻路，直到清空可用点
            # print('start point connect to: ', self.vertexDict[currentVertexName].connectTo)
            for key in self.vertexDict[currentVertexName].connectTo:
                currentDistance = self.vertexDict[currentVertexName].distance
                nextWeight = self.vertexDict[currentVertexName].connectTo[key]
                # 如果从当前点到达此点的距离，小于当前（其他）路线到达此点的距离，则将到达该点的路径（上一个点）改为当前点，并更新到达该点的最短距离
                if currentDistance + nextWeight < self.vertexDict[key].distance:
                    self.vertexDict[key].distance = currentDistance + nextWeight
                    self.vertexDict[key].lastVertexKey = currentVertexName
                    # 将该点加入到可用点列表中
                    usableDict[key] = self.vertexDict[key].distance
            # 从该点出发可到达的点都计算完毕，将该点从可用点中移除
            del usableDict[currentVertexName]

        return self.vertexDict[toVertex].distance, self.getPathStr(toVertex)

    def getShortest(self, usableDict):
        currentDistance = MAX_INT
        currentVertex = ''
        for v in usableDict:
            if usableDict[v] < currentDistance:
                currentDistance = usableDict[v]
                currentVertex = v
        return currentVertex

    def getPathStr(self, vertexKey='start'):
        resultStr = str(vertexKey)
        currentKey = vertexKey
        while self.vertexDict[currentKey].lastVertexKey is not None:
            if self.vertexDict[currentKey].lastVertexKey == 'start':
                break
            resultStr = str(self.vertexDict[currentKey].lastVertexKey) + '->' + resultStr
            currentKey = self.vertexDict[currentKey].lastVertexKey
        resultStr = 'Shortest path from \'start\' to ' + str(vertexKey) + ' is:\n\t' + resultStr

        return resultStr

    def getPathList(self, vertexKey='start'):
        resultList = [vertexKey]
        currentKey = vertexKey
        while self.vertexDict[currentKey].lastVertexKey is not None:
            if self.vertexDict[currentKey].lastVertexKey == 'start':
                break
            resultList.insert(0, self.vertexDict[currentKey].lastVertexKey)
            currentKey = self.vertexDict[currentKey].lastVertexKey
        return resultList
